Giải thuật Euclid dùng để tính ước chung lớn nhất (ƯCLN) của hai số tự nhiên a và b. Ước chung lớn nhất g là số lớn nhất chia được bởi cả a và b mà không để lại số dư và được ký hiệu là ƯCLN(a, b) hoặc (a, b).[1]

Nếu ƯCLN(a, b) = 1 thì a và b được gọi là hai số nguyên tố cùng nhau.[2] Tính chất này không khẳng định a và b là số nguyên tố.[3] Chẳng hạn, 6 và 35 đều không phải là số nguyên tố vì chúng đều có thể được phân tích thành tích của các thừa số nguyên tố: 6 = 2 × 3 và 35 = 5 × 7. Tuy nhiên, 6 và 35 nguyên tố cùng nhau vì chúng không có một thừa số chung nào.

Một hình chữ nhật kích thước 24 × 60 được chia thành 10 hình vuông nhỏ cạnh 12, trong đó 12 là ƯCLN của 24 và 60. Tổng quát hơn, một hình chữ nhật kích thước a × b có thể được chia thành các hình vuông cạnh c khi và chỉ khi c là ước chung của a và b.

Gọi g = ƯCLN(a, b). Vì a và b đều là bội của g nên chúng có thể được viết thành a = mg và b = ng, và không tồn tại số G > g nào để các biểu thức trên đúng. Hai số tự nhiên m và n phải nguyên tố cùng nhau vì có thể phân tích bất kỳ thừa số chung nào từ m và n để g lớn hơn. Do đó, một số c bất kỳ chia được bởi a và b cũng chia được bởi g. Ước chung lớn nhất g của a và b là ước chung (dương) duy nhất của chúng có thể chia được bởi một ước chung c bất kỳ.[4]

ƯCLN có thể được minh họa như sau.[5] Xét một hình chữ nhật có kích thước là a × b và một ước chung c bất kỳ có thể chia được hết cả a và b. Cả hai cạnh của hình chữ nhật có thể được chia thành các đoạn thẳng bằng nhau có độ dài là c để chia hình chữ nhật thành các hình vuông có cạnh bằng c. Ước chung lớn nhất g chính là giá trị lớn nhất của c để điều này có thể xảy ra. Chẳng hạn, một hình chữ nhật có kích thước 24 × 60 có thể được chia thành các hình vuông có cạnh là 1, 2, 3, 4, 6 hoặc 12, nên 12 là ước chung lớn nhất của 24 và 60, tức là hình chữ nhật trên có hai hình vuông nằm trên một cạnh (24/12 = 2) và năm hình vuông nằm trên cạnh còn lại (60/12 = 5).

Ước chung lớn nhất của hai số a và b là tích của các thừa số nguyên tố chung của hai số đã cho, trong đó một thừa số có thể được nhân lên nhiều lần, chỉ khi tích của các thừa số đó chia được cả a và b.[6] Chẳng hạn, ta phân tích được 1386 = 2 × 3 × 3 × 7 × 11 và 3213 = 3 × 3 × 3 × 7 × 17 nên ước chung lớn nhất 1386 và 3213 bằng 63 = 3 × 3 × 7 (là tích của các thừa số nguyên tố chung). Nếu hai số không có một thừa số nguyên tố chung nào thì ước chung lớn nhất của chúng bằng 1 (một trường hợp của tích rỗng), hay nói cách khác chúng nguyên tố cùng nhau. Một ưu điểm quan trọng của giải thuật Euclid là nó có thể tính được ƯCLN đó mà không cần phân tích ra thừa số nguyên tố.[7][8] Bài toán phân tích các số nguyên lớn là rất khó và tính bảo mật của nhiều giao thức mật mã phổ biến được dựa trên tính chất này.[9]

Một định nghĩa khác của ƯCLN rất hữu ích trong toán cao cấp, đặc biệt là lý thuyết vành.[10] Ước chung lớn nhất g của hai số a và b khác không là tổ hợp tuyến tính tích phân nhỏ nhất, tức là số nhỏ nhất với dạng ua + vb với u và v là số nguyên. Tập hợp tất cả các tổ hợp tuyến tính tích phân của a và b thực chất giống với tập hợp tất cả các bội của g (mg với m là số nguyên). Trong ngôn ngữ toán học hiện đại, ideal tạo bởi a và b chính là ideal tạo bởi g (một ideal tạo bởi một phần tử duy nhất được gọi là ideal chủ yếu và tất cả ideal của số nguyên đều là ideal chủ yếu). Từ đó, một số tính chất của ƯCLN có thể được nhận ra dễ dàng hơn, ví dụ như bất kỳ ước chung nào của a và b cũng chia được bởi ƯCLN (cả hai số hạng trong ua + vb). Tính thống nhất của định nghĩa này với các định nghĩa khác được mô tả dưới đây.

ƯCLN của ba số trở lên bằng tích của các thừa số nguyên tố chung của cả ba số đã cho,[11] nhưng nó cũng có thể được tính bằng cách tìm ƯCLN của từng cặp số trong ba số đó.[12] Chẳng hạn,

ƯCLN(a, b, c) = ƯCLN(a, ƯCLN(b, c)) = ƯCLN(ƯCLN(a, b), c) = ƯCLN(ƯCLN(a, c), b).

Vì vậy, giải thuật Euclid, vốn dùng để tính ƯCLN của hai số nguyên cũng có thể được áp dụng để tính ƯCLN của một số lượng số nguyên bất kỳ.